Error correction coding, also known as channel coding is essentially the process of adding redundancy to the original data that is to be transmitted or stored, with primal goal to reduce the probability that errors may occur. A general communication system Sys can be represented as in FIG. 1 where the transmitter Tra sends data over a noisy channel Ch and the receiver Rec has the task to identify the transmitted stream. The presence of noise within the channel perturbs the transmitted signal and generates errors. One way to guarantee the reliability of the receiver's decisions is to increase the transmitted signal power, or in other words to increase the ratio of the signal over the noise power. Another way is to minimise the rate of transmission, i.e. to minimise the bandwidth and consequently the noise. However, any of these approaches would set a barrier to the practical use of wireless communications. The work of Shannon in early '40s showed that it is possible to communicate reliably at rates very close to the capacity limits of a given channel, as long as error correction coding is used. So, application of error correction coding offers the potential for low power, high data rate reliable communications.
In addition to the k information data (which may be symbols depending of the system), p additional data are transmitted. Those p additional data, known as redundancy data, are chosen by the encoder Enc in such a way that for the particular k data, some well known rules are satisfied. The k+p data are then transmitted and the decoder Dec that is aware of the encoding rules, checks if they are satisfied. If yes, the received data is correct. If not, it means that one or more of the k information data have been received in error. Based on the same rules, the decoder must then decide which are the most probable values for the k transmitted data.
In a practical communication system binary symbols called bits 1 and 0 are used. The rules are now a set of parity check equations that should be equal to zero under modulo-2 arithmetic's. The structure of the code defines which bits participate in which equation. A sequence v is considered as a codeword when:HvT=0  (1)
The p rows of the parity check matrix H of a code defines the set of the p parity check equations. An entry of 1 in the position hij of the parity check matrix means that the code bit with index j participates in the ith parity check equation.
The H matrix can be seen as a system of equations where modulo-2 arithmetic's apply and parity bits are the unknowns. Encoding is equivalent to solving this system and finding its unique solution (the parity bits values). This is done by pure calculus techniques like the Gaussian elimination method.
The known Gaussian elimination technique may be used to bring the H matrix in encodable form, i.e. a triangular form. Unfortunately, the process of triangulation becomes highly complex even for code lengths of low to moderate size. Gaussian elimination does not guarantee success at once and very often the resulted matrix may not be full rank and have the form of FIG. 2 where g is the “gap” parameter which is a kind of measure of the “distance” of the parity check matrix to a triangular matrix. In the case where after the Gaussian elimination operation the gap is larger than zero, the only solution is to swap columns in the original H matrix and re-apply Gaussian elimination. It can be concluded that, even for a moderate size code, the number of available column swap combinations is huge.
Consequently, triangulation of the H matrix might prove to be a lengthy and complex task. T. J. Richardson and R. L. Urbanke in the article “Efficient encoding of low-density parity-check codes”, IEEE Transactions on Information theory, Vol. 47, No. 2, pages 638-656, February 2001, propose various versions of the “Greedy algorithms” to ensure that the approximate lower triangular at the beginning of the algorithm has minimum gap.
Numerous coding families have been proposed since Shannon theory of information.
Thus known are the convolutional codes (which can, in particular, implement trellis coding systems, according to the Viterbi algorithm), or even the coding scheme routinely called “turbo-code”, proposed in 1993 by C. Berrou and A. Glavieux, for example in the article “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes” (proof readings of the ICC'93, May 1993, p 1064 to 1070). This technique has been the subject of numerous studies and improvements.
Also known is the family of codes known as the LDPC (“Low-Density Parity Check”) codes invented by Gallager in 1960, generalised by Tanner in 1981 and rediscovered in 1995. LDPC codes are defined by a parity check matrix H that is sparse, i.e. comprises very few 1s and many 0s for binary codes. In case of binary codes, the data are generally designated by the term bits and in place of redundancy data the terms parity bits are generally used.
The turbo-codes and LDPC codes, and, more generally, all concatenated codes, offer performance levels in correction terms that are remarkable, for large block sizes, in particular for blocks of at least a few thousand or tens of thousands of information data (which may be bits depending of the system).
Unfortunately, manipulating such blocks of information data involves highly complex computation in decoding, which in practice turns out to be compatible only with microprocessors with considerable computing capability which are consequently relatively costly.
Furthermore, these structures are not powerful in error correcting terms for small-size blocks, for example blocks of around a hundred or a thousand data.
Although efficient and sophisticated, the triangulation method is still complex for TLDPC encoding. Moreover, this method has major drawbacks.
First, it necessitates storing the H parity check matrix in order to perform encoding. This evolves memory requirement whose size and cost increase with block-length codes.
Second, because of Gaussian elimination it tends to increase density of the H parity check matrix, in other words the number of 1's relative to the size of the matrix. A dense matrix has many 1's, hence many bits participating on the parity checks. That means that the encoder would require a large number of connections and logic gates. That would add up to the cost, to the chip area utilisation and to the power consumption of the chip. Additionally, the increased density of the matrix would contribute to increase the memory requirement, as only the non-zero positions of the matrix are stored.
TLDPC (Trellis Low Density Parity Check) codes were introduced by I. Andriyanova, J. P. Tillich and J. C. Carlach in the article “Asymptotically good codes with high iterative decoding performances”, ISIT'05, pages 850-854, IEEE September 2005 as a new family of asymptotically good LDPC codes that combine low complexity decoding and superior performance. The construction starts with a binary code of length m called the base code and yields a code of smaller length n with the help of degree distribution Λ=(λ1, λ2, K, λs) over the set of integers {1, 2, K, s} so that λi×n is an integer for any iε{1, 2, K, s} and such that nΣi=1siλi=m. Initially, the construction creates a bipartite graph between two sets U and W of length n and m respectively. The set U represents the actual code under construction while the set W represents the base code. A node in the graph represents a bit. The degree of any vertex in W is exactly one and the number of vertexes in U of degree i is λi×n. In other words, the base code set W includes multiple replicas of the vertexes of U with respect to the chosen degree distribution Λ(x). A vertex in U is linked with λi vertexes of W. Λ(x) expresses the degree distribution in a compact polynomial form:Λ(x)=a0+a1x+a2x2+K+anxn  (2)
The power of the element xi denotes degree i+1 and the constants ai, the percentage of the total edges that belong to a node of the denoted degree. As an example Λ(x)=0.7x+0.3x11 means that 70% of the edges belong to nodes of degree two and 30% to nodes of degree twelve. Similarly, Λ(x)=x denotes that all nodes have degree two. FIG. 3 shows the bipartite graph of a code of block length n=10 and degree distribution profile Λ(x)=x.
One of the main advantages of TLDPC codes is the low complexity decoding which is a result of the very simple two-state trellis representation of these codes. A two-state trellis is a two level trellis. Thus a transition from one node to another will either point towards the same level or to the other one.
The base code bits are arranged along the trellis with respect to the rules that have been described in the previous article and in a second article of the same authors “A new family of asymptotically good codes with high iterative decoding performances”, ICC'06, June 2006. These rules give indications to avoid designing bad codes (with very low minimum distance). There are several families of TLDPC codes, each differing on the number of bits that are accommodated on each trellis section. The trellis diagram of the code derived from the bipartite graph of FIG. 3 is shown in FIG. 4. The different families disclose in the previous article “A new family of asymptotically good codes with high iterative decoding performances”, ICC'06, pages 1177 to 1182, June 2006 are called respectively A, B, C, D and E.
The trellis of the Family-A TLDPC codes with bits of degree-one is defined as follows: there are r sections with indexes i={0, 1, K, r−1}. Those sections i where i(mod 3)=0, carry one bit. In other words they are degree-one sections. All remaining sections carry two bits. The number of degree-one sections is identical with the number of degree-one bits. The generated codes have rate 0.5.
Family-E TLDPC codes trellis structure differs from family-A structure in the number and position of degree-one sections along the trellis. Since the number of degree-one sections is identical with the number of degree-one bits, this changes too. There are r trellis sections with indexes i={0, 1, K, r−1}. All sections carry two bits except of those sections whose index i satisfies i(mod 5)=0 which carry one bit.
Family-C TLDPC codes have more sections and bits of degree-one than family-E, but less than family-A. From the r sections of the trellis with index i={0, 1, K, r−1} only those sections with index such that i(mod 4)=0 are degree-one sections. The trellis permutation is constructed exactly as in families A and E.
The trellis of TLDPC codes exhibits two major characteristics, namely:
transition from current state t to the following state t+1 is not associated with a unique path,
the values of the current state and the input bit are not sufficient for determining the next state.
An outcome of these two statements is that an input sequence starting from a fixed state can be represented in the trellis by multiple paths. To state it in a different way, a certain path in the trellis is not associated with a unique base codeword. Consequently, attempting to encode by tracking down the candidate paths on the trellis is a very difficult task even for very short codes because the number of candidate paths grows rapidly. Furthermore there's no certainty that there will be a path on the base code trellis that will yield a valid codeword of length n, i.e. a path along which all multiple replicas of an actual code bit are identical.
The following example helps describing this problem. The task is to encode the code that is derived from the bipartite graph of FIG. 3 and yields the base code trellis of FIG. 4. The degree distribution is Λ(x)=x, which means that all bits have degree two. The length n of the code is ten of which five are information bits and five parity bits. The bits ui with indexes from five to nine are considered as information bits; hence the information to be sent is accommodated to these bits. The remaining bits ui with indexes from zero to four are the parity bits. The encoding process has to encode the message {u5u6u7u8u9}={01101}. After substituting the information bits values on the base code trellis, the trellis becomes as in FIG. 5. Given the values and the position of the information bits, some of the paths cannot exist and are removed from the trellis. However, there are still many available paths and for encoding to be successful there must be found a path that satisfies all ui pairs. Clearly, even for such a short code the complexity of the encoding procedure is high and increases exponentially with the block-length. Moreover, it is not guaranteed that a code exists for a certain permutation that means for the chosen arrangement of the bits along the base code trellis.